{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Remove Palindromic Subsequences"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #two-pointers #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #双指针 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: removePalindromeSub"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #删除回文子序列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串&nbsp;<code>s</code>，它仅由字母&nbsp;<code>'a'</code> 和 <code>'b'</code>&nbsp;组成。每一次删除操作都可以从 <code>s</code> 中删除一个回文 <strong>子序列</strong>。</p>\n",
    "\n",
    "<p>返回删除给定字符串中所有字符（字符串为空）的最小删除次数。</p>\n",
    "\n",
    "<p>「子序列」定义：如果一个字符串可以通过删除原字符串某些字符而不改变原字符顺序得到，那么这个字符串就是原字符串的一个子序列。</p>\n",
    "\n",
    "<p>「回文」定义：如果一个字符串向后和向前读是一致的，那么这个字符串就是一个回文。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"ababa\"\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>字符串本身就是回文序列，只需要删除一次。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"abb\"\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>\"<strong>a</strong>bb\" -&gt; \"<strong>bb</strong>\" -&gt; \"\". \n",
    "先删除回文子序列 \"a\"，然后再删除 \"bb\"。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"baabb\"\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>\"<strong>baa</strong>b<strong>b</strong>\" -&gt; \"b\" -&gt; \"\". \n",
    "先删除回文子序列 \"baab\"，然后再删除 \"b\"。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 1000</code></li>\n",
    "\t<li><code>s</code> 仅包含字母&nbsp;<code>'a'</code>&nbsp; 和 <code>'b'</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [remove-palindromic-subsequences](https://leetcode.cn/problems/remove-palindromic-subsequences/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [remove-palindromic-subsequences](https://leetcode.cn/problems/remove-palindromic-subsequences/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"ababa\"', '\"abb\"', '\"baabb\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 本题只需要判断字符串是否回文，回文就一次删完，返回1，不回文就一次删a，一次删b，两次删完，返回2\n",
    "class Solution:\n",
    "    def removePalindromeSub(self, s: str) -> int:\n",
    "        return 1 if s == s[::-1] else 2\n",
    "\n",
    "class Solution:\n",
    "    def removePalindromeSub(self, s: str) -> int:\n",
    "        for i in range(len(s) // 2):\n",
    "            if s[i] != s[len(s) - i - 1]:\n",
    "                return 2\n",
    "        return 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removePalindromeSub(self, s: str) -> int:\n",
    "        if s == '':\n",
    "            return 0\n",
    "\n",
    "        if s == s[::-1]:\n",
    "            return 1\n",
    "        return 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removePalindromeSub(self, s: str) -> int:\n",
    "        return 1 if s == s[::-1] else 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removePalindromeSub(self, s: str) -> int:\n",
    "        return (s != s[::-1]) + 1\n",
    "\n",
    "\n",
    "                        \n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removePalindromeSub(self, s: str) -> int:\n",
    "        return 1 if s==s[::-1] else 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removePalindromeSub(self, s: str) -> int:\n",
    "        return 1 if s == s[::-1] else 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removePalindromeSub(self, s: str) -> int:\n",
    "        return 1 if s == s[::-1] else 2\n",
    "\n",
    "# 作者：力扣官方题解\n",
    "# 链接：https://leetcode.cn/problems/remove-palindromic-subsequences/solutions/1220916/shan-chu-hui-wen-zi-xu-lie-by-leetcode-s-tqtb/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removePalindromeSub(self, s: str) -> int:\n",
    "        if s==s[::-1]:\n",
    "            return 1\n",
    "        else:\n",
    "            return 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removePalindromeSub(self, s: str) -> int:\n",
    "        if s == ''.join(reversed(s)):\n",
    "            return 1\n",
    "        return 2\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def removePalindromeSub(self, s: str) -> int:\n",
    "        if s == s[::-1]:\n",
    "            return 1\n",
    "        return 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removePalindromeSub(self, s: str) -> int:\n",
    "        if not s:\n",
    "            return 0\n",
    "        n = len(s)\n",
    "        i, j = 0, n-1\n",
    "        while i < j:\n",
    "            if s[i] != s[j]: # 不然分2次，1次全删a, 1次全删b\n",
    "                return 2\n",
    "            i += 1\n",
    "            j -=1\n",
    "        return 1 # 如果s本身回文，1次删\n",
    "    \n",
    "\"\"\"\n",
    " Subsequences 不需要连续\n",
    "如果是回文字符串答案是1，如果不是，先删除所有a再删除所有b，答案是2\n",
    "\"\"\"\n",
    "\n",
    "     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removePalindromeSub(self, s: str) -> int:\n",
    "        return (s != s[::-1]) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removePalindromeSub(self, s: str) -> int:\n",
    "        if len(s) == 0:\n",
    "            return 0\n",
    "        elif s[0] != s[-1]:\n",
    "            return 2\n",
    "        else:\n",
    "            k, n, res, i = 0, len(s), 0, 0\n",
    "            while i < n:\n",
    "                j = n - 1\n",
    "                while i <= j:\n",
    "                    k = j\n",
    "                    t = i\n",
    "                    f = 0\n",
    "                    while s[i] == s[j]:\n",
    "                        if i >= j:\n",
    "                            res += 1\n",
    "                            f = 1\n",
    "                            j = k\n",
    "                            break\n",
    "                        i += 1\n",
    "                        j -= 1\n",
    "                    if f == 0:\n",
    "                        j = k - 1\n",
    "                        i = t\n",
    "                    else:\n",
    "                        i = j + 1\n",
    "            return res if res<=2 else 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removePalindromeSub(self, s: str) -> int:\n",
    "        if len(s)==0:\n",
    "            return 0\n",
    "        elif s==s[::-1]:\n",
    "            return 1\n",
    "        else:\n",
    "            return 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removePalindromeSub(self, s: str) -> int:\n",
    "        k, n, res, i = 0, len(s), 0, 0\n",
    "        while i < n:\n",
    "            j = n - 1\n",
    "            while i <= j:\n",
    "                k = j\n",
    "                t = i\n",
    "                f = 0\n",
    "                while s[i] == s[j]:\n",
    "                    if i >= j:\n",
    "                        res += 1\n",
    "                        f = 1\n",
    "                        j = k\n",
    "                        break\n",
    "                    i += 1\n",
    "                    j -= 1\n",
    "                if f == 0:\n",
    "                    j = k - 1\n",
    "                    i = t\n",
    "                else:\n",
    "                    i = j + 1\n",
    "        return res if res<=2 else 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removePalindromeSub(self, s: str) -> int:\n",
    "        return 1 if s == s[::-1] else 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removePalindromeSub(self, s: str) -> int:\n",
    "        if s == s[::-1]:\n",
    "            return 1\n",
    "        return 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removePalindromeSub(self, s: str) -> int:\n",
    "        return 1 if s == s[::-1] else 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removePalindromeSub(self, s: str) -> int:\n",
    "        i=0\n",
    "        while i*2<len(s):\n",
    "            if s[i]!=s[-1-i]:\n",
    "                return 2\n",
    "            i+=1\n",
    "        return 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removePalindromeSub(self, s: str) -> int:\n",
    "        if set([v for v in s]) == 1:\n",
    "            return 0\n",
    "        l,r = 0,len(s) - 1\n",
    "        while l < r:\n",
    "            if s[l] == s[r]:\n",
    "                l += 1\n",
    "                r -= 1\n",
    "            else:\n",
    "                break\n",
    "        if l == r or r + 1 == l:\n",
    "            return 1\n",
    "        return 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removePalindromeSub(self, s: str) -> int:\n",
    "        s2=list(s)\n",
    "        s2.reverse()\n",
    "        s2=''.join(s2)\n",
    "        if(s2==s):\n",
    "            return 1\n",
    "        return 2\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removePalindromeSub(self, s: str) -> int:\n",
    "        return 1 if s==s[::-1]else 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removePalindromeSub(self, s: str) -> int:\n",
    "        return 1 if s==s[::-1] else 2\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removePalindromeSub(self, s: str) -> int:\n",
    "        left=0\n",
    "        right=len(s)-1\n",
    "        status=True\n",
    "        ans=0\n",
    "        while left<right:\n",
    "            if s[left]!=s[right]:\n",
    "                status=False\n",
    "            left+=1\n",
    "            right-=1\n",
    "            \n",
    "        if status==True:\n",
    "            ans=1\n",
    "        else:\n",
    "            ans=2\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removePalindromeSub(self, s: str) -> int:\n",
    "        def dis(x:str)->bool:\n",
    "            l,r=0,len(x)-1\n",
    "            while l<r:\n",
    "                if x[l]==x[r]:\n",
    "                    l+=1\n",
    "                    r-=1\n",
    "                else:\n",
    "                    return False\n",
    "            return True\n",
    "        count=0\n",
    "        for i in range(len(s)-1,-1,-1):\n",
    "            for j in range(len(s)-i):\n",
    "                s=s[j:j+i+1]\n",
    "                if dis(s):\n",
    "                    s=s[:j]+s[j+i+1:]\n",
    "                    count+=1\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removePalindromeSub(self, s: str) -> int:\n",
    "        return 1 if s == s[::-1] else 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removePalindromeSub(self, s: str) -> int:\n",
    "        return 1 if s == s[::-1] else 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removePalindromeSub(self, s: str) -> int:\n",
    "        return (s!=s[::-1])+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removePalindromeSub(self, s: str) -> int:\n",
    "        return 1 if s == s[::-1] else 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def removePalindromeSub(self, s: str) -> int:\r\n",
    "        if s == s[::-1]:\r\n",
    "            return 1\r\n",
    "        else:\r\n",
    "            return 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removePalindromeSub(self, s: str) -> int:\n",
    "        return 1 if s==s[::-1] else 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removePalindromeSub(self, s: str) -> int:\n",
    "        return 1 if s==s[::-1] else 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removePalindromeSub(self, s: str) -> int:\n",
    "        return 1 if s == s[::-1] else 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removePalindromeSub(self, s: str) -> int:\n",
    "        if s == s[::-1]:\n",
    "            return 1\n",
    "        return 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removePalindromeSub(self, s: str) -> int:\n",
    "        \"\"\"\n",
    "            回文子序列 比较难处理\n",
    "\n",
    "        \"\"\"\n",
    "        return 1 if s == s[::-1] else 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removePalindromeSub(self, s: str) -> int:\n",
    "        a=2\n",
    "        if s==s[::-1]:\n",
    "            a=1\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removePalindromeSub(self, s: str) -> int:\n",
    "        return 1 if s == s[::-1] else 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removePalindromeSub(self, s: str) -> int:\n",
    "        # 最多两次最少一次（两种字符自身就是回文子序列）\n",
    "        return 1 if s==s[::-1] else 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removePalindromeSub(self, s: str) -> int:\n",
    "        left=0\n",
    "        right=len(s)-1\n",
    "        status=True\n",
    "        ans=0\n",
    "        while left<right:\n",
    "            if s[left]!=s[right]:\n",
    "                status=False\n",
    "            left+=1\n",
    "            right-=1\n",
    "            \n",
    "        if status==True:\n",
    "            ans=1\n",
    "        else:\n",
    "            ans=2\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removePalindromeSub(self, s: str) -> int:\n",
    "\n",
    "\n",
    "\n",
    "        return 1 if s == s[::-1] else 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removePalindromeSub(self, s: str) -> int:\n",
    "        # 1.空字符串 删除0次 2.回文字符串 删除1次 3.非回文字符串 删除2次 （一次删除全部 a , 一次删除全部b）\n",
    "        return (1 if s==s[::-1] else 2) if s else 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removePalindromeSub(self, s: str) -> int:\n",
    "        return 1 if s == s[::-1] else 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removePalindromeSub(self, s: str) -> int:\n",
    "        i,j = 0,len(s)-1\n",
    "        while i<j:\n",
    "            if s[i]==s[j]:\n",
    "                i+=1\n",
    "                j-=1\n",
    "            else:\n",
    "                return 2\n",
    "        return 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removePalindromeSub(self, s: str) -> int:\n",
    "        if s == s[::-1]:\n",
    "            return 1\n",
    "        return 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removePalindromeSub(self, s: str) -> int:\n",
    "        return 1 + (s != s[::-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removePalindromeSub(self, s: str) -> int:\n",
    "        if s == s[::-1]:\n",
    "            return 1\n",
    "        else:\n",
    "            return 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removePalindromeSub(self, s: str) -> int:\n",
    "        return 1 if s == s[::-1] else 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removePalindromeSub(self, s: str) -> int:\n",
    "        if s == s[::-1]:\n",
    "            return 1\n",
    "        else:\n",
    "            return 2 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removePalindromeSub(self, s: str) -> int:\n",
    "        return (s != s[::-1]) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removePalindromeSub(self, s: str) -> int:\n",
    "        for i in range(len(s) // 2 + 1):\n",
    "            if s[i] != s[-1-i]:\n",
    "                return 2\n",
    "        return 1\n",
    "\n",
    "class Solution:\n",
    "    def removePalindromeSub(self, s: str) -> int:\n",
    "        n = len(s) // 2\n",
    "        return 1 + (s[:n+1] != s[-n-1:][::-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removePalindromeSub(self, s: str) -> int:\n",
    "        for i in range(len(s) // 2 + 1):\n",
    "            if s[i] != s[-1-i]:\n",
    "                return 2\n",
    "        return 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removePalindromeSub(self, s: str) -> int:\n",
    "        return 1 if s == s[::-1] else 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removePalindromeSub(self, s: str) -> int:\n",
    "        if not s:\n",
    "            return 0\n",
    "        if s ==s[::-1]:\n",
    "            return 1\n",
    "        else:\n",
    "            return 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removePalindromeSub(self, s: str) -> int:\n",
    "        if(s == s[::-1]):\n",
    "            return 1\n",
    "        else:\n",
    "            return 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removePalindromeSub(self, s: str) -> int:\n",
    "        return (s != s[::-1]) + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removePalindromeSub(self, s: str) -> int:\n",
    "        if not s:\n",
    "            return 0\n",
    "        elif s == s[::-1]:\n",
    "            return 1\n",
    "        else:\n",
    "            return 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removePalindromeSub(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        \n",
    "        i, j = 0, n - 1\n",
    "        \n",
    "        while i < j and s[i] == s[j]:\n",
    "            i += 1\n",
    "            j -= 1\n",
    "            \n",
    "        return 1 if i >= j else 2\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removePalindromeSub(self, s: str) -> int:\n",
    "        left=0\n",
    "        right=len(s)-1\n",
    "        status=True\n",
    "        ans=0\n",
    "        while left<right:\n",
    "            if s[left]!=s[right]:\n",
    "                status=False\n",
    "            left+=1\n",
    "            right-=1\n",
    "            \n",
    "        if status==True:\n",
    "            ans=1\n",
    "        else:\n",
    "            ans=2\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removePalindromeSub(self, s: str) -> int:\n",
    "        def dis(x:str)->bool:\n",
    "            l,r=0,len(x)-1\n",
    "            while l<r:\n",
    "                if x[l]==x[r]:\n",
    "                    l+=1\n",
    "                    r-=1\n",
    "                else:\n",
    "                    return False\n",
    "            return True\n",
    "        count=0\n",
    "        for i in range(len(s)-1,-1,-1):\n",
    "            for j in range(len(s)-i):\n",
    "                s=s[j:j+i+1]\n",
    "                if dis(s):\n",
    "                    s=s[:j]+s[j+i+1:]\n",
    "                    print(count)\n",
    "                    count+=1\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removePalindromeSub(self, s: str) -> int:\n",
    "        if s==s[::-1]:\n",
    "            return 1\n",
    "        else:\n",
    "            return 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removePalindromeSub(self, s: str) -> int:\n",
    "        if 'a' and 'b' in s:\n",
    "            if s == s[::-1]:\n",
    "                return 1\n",
    "            else:\n",
    "                return 2\n",
    "        elif not s:\n",
    "            return 0\n",
    "        else:\n",
    "            return 1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removePalindromeSub(self, s: str) -> int:\n",
    "        if s == s[::-1]:\n",
    "            return 1\n",
    "        else:\n",
    "            return 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removePalindromeSub(self, s: str) -> int:\n",
    "        return 1 if s == s[::-1] else 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removePalindromeSub(self, s: str) -> int:\n",
    "        return 1 if s == s[::-1] else 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removePalindromeSub(self, s: str) -> int:\n",
    "        if s == s[::-1]:\n",
    "            return 1\n",
    "        else:\n",
    "            return 2"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
